\documentclass[11pt,letterpaper]{article}

\newcommand{\mytitle}{CS254 Homework 1}
\newcommand{\myauthor}{Kevin Lewi}
\date{January 20, 2011}

\usepackage{hwformat}

\begin{document}

\maketitle

\section*{Problem 1}

\newcommand{\prefix}{\operatorname{prefix}}

\begin{lem}
	If $E \neq NE$ then $P \neq NP$.
\end{lem}

\begin{proof}
	We will use $\mathcal{N} = 2^{O(n)}$.

	First let $L$ be a language such that $L \in NE$. So, there exists a 
	non-deterministic machine $M$ that accepts $L$. Let $n$ be the length of the 
	input --- then, $M$ runs in time $\mathcal{N}$.

	Now, consider the language $L'$ that takes inputs of length $\mathcal{N}$. 
	Define $\prefix_n(x)$ to be the string representing the first $n$ bits of $x$.
	Here, $x \in L'$ if $\prefix_n(x) \in L$ and all other bits of $x$ are $0$, 
	and $x \not\in L$ otherwise. In other words, $L'$ accepts exactly the inputs 
	that $L$ accepts, except that each of the accepting inputs is padded with 
	$\mathcal{N} - n$ $0$'s.

	Now, we construct a non-deterministic machine $M'$ that is the exact same as 
	$M$, except that it first checks to see if the last $\mathcal{N}-n$ bits are 
	all $0$'s. If this is the case, and $M$ would normally accept $\prefix_n(x)$, 
	then $M'$ accepts the input. Otherwise, it rejects.

	Now, note that $M'$ is non-deterministic, runs in time $O(\mathcal{N})$, and 
	its inputs are of length $\mathcal{N}$. Since it decides $L'$, we can conclude 
	that $L' \in NP$.

	Now, we will show the contrapositive of the lemma. If $P = NP$, then $L' \in 
	P$. Let $M_2$ be the deterministic machine that decides $L'$ and runs in time 
	polynomial in the length of the inputs, $\mathcal{N}$. We will construct a 
	final machine $M_3$ that decides $L$ (the original language that we assumed to 
	be in $NE$) as follows: given input $x$, it will append $\mathcal{N}-n$ $0$'s 
	to the end of $x$, and then simulate the computation of $M_2$ on the modified 
	input. One can perform this simulation in time polynomial in $\mathcal{N}$, 
	since $M_2$ runs in time polynomial in $\mathcal{N}$. Thus, we have shown that 
	$L \in E$.

	Note that we have shown that if $P = NP$, then every language in $NE$ is also 
	in $E$. Thus, the contrapositive yields the lemma.
\end{proof}

\section*{Problem 2}

\begin{lem}
	Assume $P = NP$. Let $L$ be the language that takes a CNF $f$, a string of 
	bits $s$, and an integer $k$. So, the input is a triple $(f,s,k)$ and $L$ 
	accepts if there exists an equivalent CNF of length less than $k$ whose first 
	$|s|$ bits match $s$, exactly. Then, $L \in NP$ (and hence, $L \in P$).
\end{lem}

\begin{proof}
	If $x \in L$, then let $y$ be the encoding of a CNF equivalent to $f$ that has 
	length less than $f$. It is of length polynomial in the size of the input, so 
	there exists a YES-certificate for this problem. Now, if $x \not\in L$, we 
	need to show that no such certificate allows the machine to accept. Thus, it 
	remains to show that one can verify that a candidate proof encoding a CNF $g$ 
	is indeed equivalent to $f$, has prefix $s$, and is of length less than $k$, 
	all in polynomial time.

	To see this, let $L_2$ be the language that takes as input two CNFs $f$ and 
	$g$ accepts if they are \emph{not} equivalent. This problem is in NP, because 
	one can provide an assignment of variables such that the two CNFs disagree in 
	output, and this represents a YES-certificate. Since we are assuming that $P = 
	NP$, we can conclude that this problem is also in $P$. Thus, one can determine 
	if two CNFs are equivalent in polynomial time, assuming $P = NP$. Clearly, the 
	length of the CNFs and whether or not a prefix matches $s$ can be determined 
	in polynomial time, so this completes the proof for the main lemma, since we 
	have established that the validity of the certificate can be verified in 
	polynomial time.
\end{proof}

\begin{lem}
	If $P = NP$, then Min-Equiv-CNF is solvable in polynomial time.
\end{lem}

\begin{proof}
	Under the $P = NP$ assumption, the previous lemma acts as the appropriate 
	decision problem for this function problem. Consider the following procedure, 
	where we end up outputting a binary encoding for the minimal equivalent CNF to 
	a given CNF $f$:

	First, note that for fixed $f$ and $s$, we can determine the exact length of 
	the minimal equivalent CNF to $f$ with prefix $s$ by performing a binary 
	search on the third parameter $k$ (in polynomial time). Now, compare the 
	length of the minimal CNF when $s = 0$ versus when $s = 1$. If $s = 0$ results 
	in a smaller CNF, then repeat this process for $s = 00$ and $s = 01$ (and vice 
	versa for when $s = 1$ resulted in a smaller CNF). Since the length of the 
	binary encoding is polynomial in the size of the input, we still make only a 
	polynomial number of queries to the machine that accepts $L$ from the previous 
	lemma.

	Through this procedure, we can determine the exact binary encoding of the 
	minimal CNF of $f$ in polynomial time, which means that Min-Equiv-CNF is 
	solvable.
\end{proof}

\end{document}
